package com.wpp.algorithm.lagou.part1.lesson5;

import com.wpp.data_structure.MyNode;

/**
 * @author wpp25
 * @date 2021/6/9 21:27
 * @description：
 */
public class Lesson5_1 {

    public static void main(String[] args) {
        MyNode<String> node = new MyNode<>("str0");
        MyNode<String> curr = node;
        for (int i = 1; i < 6; i++) {
            MyNode<String> node1 = new MyNode<>("str" + i);
            curr.next = node1;
            curr = node1;
            /* if (i == 5) {
               node1.next = node.next.next;
            }*/
        }
        Solution solution = new Solution();

        System.out.println(solution.detectCycle(node));
    }
    /*
使用快慢指针找到是否有环（快指针一次走两步，慢指针一次走一步）
找到环以后快指针不变，慢指针再回到头结点，快慢指针都按照步长1前进，等两个指针再次相遇就是环的入口位置。
大家可以回想一个场景，在学校田径运动中，跑的快的同学会套圈跑的慢的同学，这个其实就是和快慢指针的思路很像的。

如果链表的头结点就是环的入口，那就是一个标准环形跑道，慢的人跑完一整圈，正好被那个两倍速度的套圈，也就是两个人在起点相遇，
那么如果两个人不是在起点相遇，那么相差的距离其实就是头结点到环入口的距离。
*/
    public static class Solution {
        public MyNode detectCycle(MyNode head) {
            MyNode fast = head;
            MyNode slow = head;
            while(fast != null && fast.next != null){
                fast = fast.next.next;//快指针走两步
                slow = slow.next;//慢指针走一步
                if(fast == slow)  break; //相遇代表有环
            }
            if(fast == null || fast.next == null)return null;
            slow = head;//慢指针回到链表头部
            while(fast != slow){
                slow = slow.next;
                fast = fast.next;//快指针也调整为一次走一步
            }
            return slow;
        }
    }
}
